package leetcode;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

import org.junit.Test;

public class MergeIntervals {
	public ArrayList<Interval> merge(ArrayList<Interval> intervals) {

		if (intervals == null || intervals.size() == 0)
            return intervals;
        
        Comparator<Interval> comp = new Comparator<Interval>(){
			@Override
			public int compare(Interval o1, Interval o2) {
				if (o1.start == o2.start)
					return 0;
				
				return o1.start < o2.start ? -1 : 1;
			}
        };
        
        Collections.sort(intervals, comp);
        
        ArrayList<Interval> res = new ArrayList<Interval>();
        
        for (Interval in: intervals){
            if (res.size() == 0)
                res.add(in);	
            else {
                Interval last = res.get(res.size()-1);
                if (last.end < in.start)
                    res.add(in);
                else {
                    last.start = Math.min(last.start, in.start);
                    last.end = Math.max(last.end, in.end);
                }
            }
        }
        
        return res;
        
    }
    
    public void sortIntervals(ArrayList<Interval> intervals, int h, int t){
        int pivot = intervals.get((t+h)/2).start;
        int i=h, j=t;
        
        while (i<j){
            while (intervals.get(i).start < pivot) ++i;
            while (intervals.get(j).start > pivot) --j;
            
            if (i<=j){
                Interval tmp = intervals.get(i);
                intervals.set(i, intervals.get(j));
                intervals.set(j, tmp);
                ++i;
                --j;
            }
            
            if (j>h)
                sortIntervals(intervals, h, j);
                
            if (i<t)
                sortIntervals(intervals, i, t);
        }
    }
    
    @Test
    public void testMerge(){
    	MergeIntervals mi = new MergeIntervals();
    	ArrayList<Interval> intervals = new ArrayList<Interval>();
    	//[1,3],[2,6],[8,10],[15,18],
    	intervals.add(new Interval(8,10));
    	intervals.add(new Interval(15,18));
    	intervals.add(new Interval(1,3));
    	intervals.add(new Interval(2,6));
    	System.out.println(mi.merge(intervals));
    }
}

class Interval {
     int start;
     int end;
     Interval() { start = 0; end = 0; }
     Interval(int s, int e) { start = s; end = e; }
     
     @Override
     public String toString(){
    	 return "["+start+","+end+"]";
     }
}
